package com.mzy.linear_struct;

public class Knapsack {
    public static int knapSack(int W, int wt[], int val[], int n) {
        // 创建二维数组dp，其中dp[i][w]表示在前i个物品中挑选总重量不超过w时的最大价值
        int[][] dp = new int[n + 1][W + 1];

        // 初始化，当没有物品可选或背包容量为0时，价值为0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int w = 0; w <= W; w++) {
            dp[0][w] = 0;
        }

        // 动态规划填表过程
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                // 如果当前物品的重量超过了背包的容量，那么不放入该物品
                if (wt[i - 1] > w) {
                    dp[i][w] = dp[i - 1][w];
                } else {
                    // 在放入和不放入当前物品中选择价值最大的情况
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
                }
            }
        }

        // 最终dp[n][W]就是我们要求解的结果
        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] val = {60, 100, 120}; // 物品的价值
        int[] wt = {10, 20, 30};   // 物品的重量
        int W = 50;                 // 背包的容量
        int n = val.length;         // 物品的数量

        System.out.println("最大价值: " + knapSack(W, wt, val, n));
    }
}